I expected the sequence to be returned in order, from 0 to 9.
This expectation is based only on the previous observed behavior, not on the documented behavior, so it turned out not to be a safe expectation.
The issue is that there is no documented relationship between (1) the value returned from your RNG's next() method; and (2) the result of calling Array.randomElement(using:) or Int.random(in:using:). That is, exactly how those methods "use" your RNG is undocumented, and is therefore subject to change. Sounds like randomElement() formerly used your RNG's result directly as the index for the random element, but now it does something different. Both those behaviors are valid as they fulfill the documented API contract.
(The documentation for randomElement() actually includes a note that emphasizes this undocumented-ness.)
What do I need to do in the random number generator implementation to get it to work with arrays (and ranges) correctly?
The current behavior is "correct", so let's change the question to:
What do I need to do in the RNG implementation to achieve specific desired behavior in Array.randomElement(using:) both now and in future versions of the Swift library?
The answer is: you can't.
However, you may be able to achieve your testing goals by using your RNG in a different way, such as using it to generate pseudo-random array indexes directly, to replace usage of the system's randomElement() method. Or maybe you just want to iterate directly over the collection and perform testing logic on each element. It just depends on what you're trying to do.